The present invention relates to data transmission systems and, in particular, to channel coding in such systems.
Much attention has been focused in recent years on channel codes which provide so-called coding gain. Prominent among these are the so-called "trellis" codes described in such papers as G. Ungerboeck, "Channel Coding With Multilevel/Phase Signals," IEEE Trans. Information Theory, IT-28, 1982, pages 55-67; A. R. Calderbank and N. J. A. Sloane, "A New Family of Codes for Dial-Up Voice Lines," Proc. IEEE Global Telecomm Conf., November 1984, pages 20.2.1-20.2.4; A. R. Calderbank and N. J. A. Sloane, "Four-Dimensional Modulation With an Eight-State Trellis Code," AT&T Technical Journal, Vol. 64, No. 5, May-June 1985, pages 1005-1018; A. R. Calderbank and N. J. A. Sloane, "An Eight-Dimensional Trellis Code," Proc. IEEE, Vol. 74, No. 5, May 1986, pages 757-759; and L.-F. Wei, "Rotationally Invariant Convolutional Channel Coding With Expanded Signal Space--Part I: 180 Degrees and Part II: Nonlinear Codes," IEEE J. Select. Areas Commun., Vol. SAC-2, September 1984, pages 659-686, all of which are hereby incorporated by reference.
In typical known trellis coding arrangements, n of the bits of each of a succession of (k+n)-bit input words are applied to a so-called trellis coder which, in turn, selects one of a plurality of 2.sup.m subsets of the signalling alphabet, where m&gt;n. (Other types of codes, such as the so-called Reed-Solomon codes, can be used to select the subset.) Each subset contains 2.sup.k signalling points and the other k bits, referred to herein as the non-trellis-coded bits, are used to identify a particular one of the 2.sup.k points in the selected subset as the signal point to be communicated to the receiver. So-called Viterbi decoding is then used in the receiver to recover the most likely sequence of transmitted signal points and, in turn, the (k+n)-bit input words.
Conventional block coding would require an alphabet of 2.sup.(k+n) signal points to transmit the (k+n)-bit input words. By contrast, as can be seen from the foregoing, trellis coding requires a larger alphabet of 2.sup.(k+m) signal points However, in exchange for this redundancy, a trellis code, if properly designed, will provide an increase over block coding in the minimal distance between signal points communicated to the receiver This increase, when normalized by the average transmitted signal power, is referred to as the "coding gain" which manifests itself in the form of enhanced immunity to such random channel impairments as additive noise.
It was known to those working with block codes even prior to the advent of trellis coding that the minimal distance between signal points in the alphabet--and thus the immunity to random channel impairments--can be increased for a given maximal signal power by increasing the dimensionality of the alphabet, e.g., using an eight-dimensional alphabet rather than a four- or two-dimensional alphabet. This recognition can be traced to the pioneering work of Nyquist and is illustrated in the more recent work of, for example, G. Welti in U.S. Pat. No. 4,084,137 issued Apr. 11, 1978 and A. Gersho et al in U.S. Pat. No. 4,457,004 issued June 26, 1984. It was thereafter shown that this principle was equally applicable to arrangements employing trellis codes. Specifically, trellis codes with four-dimensional modulation are shown, for example, in G. D. Forney et al, "Efficient Modulation for Band-Limited Channels, IEEE Journal on Selected Areas of Communications, Vol. SAC-2, No. 5, Sept. 1984, pp. 632-647; our aforementioned article in the AT&T Technical Journal; and our U.S. Pat. No. 4,581,601 issued Apr. 8, 1986.
One of the aspects necessary to the the design of a trellis coding arrangement is the partitioning of the selected alphabet into appropriate subsets as aforesaid. To date, the published literature and patents--which are, in the main, directed to trellis codes with two- and four-dimensional alphabets--seem to have arrived at the subsets heuristically. It becomes more difficult, however, to arrive at an advantageous partition as the dimensionality of the alphabet increases to eight and higher dimensions.